Wyznaczanie planu sieci drogowej 2

Limit pamięci: 64 MB

Bajtazar wybiera się w podróż samochodową po Bajtocji, lecz niestety ma problemy z nabyciem mapy tego kraju. Od znajomych dowiedział się o pewnych właściwościach bajtockiej sieci dróg:

• W Bajtocji jest miast, ponumerowanych od do .
• Każda droga jest dwukierunkowa i łączy pewne dwa różne miasta.
• Każde dwa różne miasta są połączone dokładnie jedną trasą, złożoną z pewnej liczby dróg, na której żadne miasto nie powtarza się.
• Z -tego miasta prowadzi dokładnie dróg.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (). Drugi wiersz zawiera liczb całkowitych ().

Wyjście

Jeżeli nie istnieje żaden plan sieci drogowej spełniający warunki z wejścia, to pierwszy i jedyny wiersz wyjścia powinien zawierać jedno słowo BRAK . W przeciwnym przypadku każdy wiersz powinien zawierać opis jednej dwukierunkowej drogi - dwie różne liczby całkowite z zakresu od do , oznaczające numery miast połączonych daną drogą. Każdą drogę należy wypisać dokładnie raz. Kolejność wypisania dróg i numerów miast połączonych drogami może być dowolna.

Przykład

Dla danych wejściowych:

6
1 1 3 3 1 1

poprawną odpowiedzią jest:

1 3
2 3
3 4
5 4
6 4

(A czy pamiętasz zadanie Wyznaczanie planu sieci drogowej z PA 2008?)

Autor zadania: Jakub Radoszewski.